/*
 * @lc app=leetcode.cn id=141 lang=typescript
 *
 * [141] 环形链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

// hash 表法
// function hasCycle(head: ListNode | null): boolean {
//     if (head === null) return false;
//     let hash = new Set<ListNode>();
//     let now = head;
//     while (now.next) {
//         if (hash.has(now)) {
//             return true;
//         } else {
//             hash.add(now);
//         }
//         now = now.next;
//     }
//     return false;
// }

// 快慢指针

function hasCycle(head: ListNode | null): boolean {
    if (head === null) return false;
    let fast = head;
    let slow = head;
    while (fast.next) {
        // 快指针为慢指针两倍速，那么进入 环的时候，快可以快慢的一圈并相遇
        if (fast.next.next) {
            fast = fast.next.next;
            slow = slow.next!;
            if (fast === slow) {
                return true;
            }
        } else {
            return false;
        }
    }
    return false;
}
// @lc code=end
